package tsp.leetcode.eyery;

import java.util.Arrays;

/**
 * leetcode: 85  最大矩形 label: 动态规划 maximal-rectongle (Hard)
 * 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 *
 * 示例:
 *
 * 输入:
 * [
 *   ["1","0","1","0","0"],
 *   ["1","0","1","1","1"],
 *   ["1","1","1","1","1"],
 *   ["1","0","0","1","0"]
 * ]
 * 输出: 6

 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximal-rectangle
 */
public class Solution64_85 {

    public static int maximalRectangle(char[][] matrix) {
        if (matrix.length==0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[]  height = new int[n];
        Arrays.fill(right,n);
        int maxare = 0;

        for (int i = 0; i < m; i++) {
            int cur_left=0,cur_right =n;
            //更新高度
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]=='1') {
                    height[j]++;
                }else {
                    height[j]=0;
                }
            }
            //更新 左边界
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]=='1'){
                    left[j] = Math.max(left[j],cur_left);
                } else{
                    left[j]=0;
                    cur_left = j+1;
                }
            }
            //更新右边界
            for (int j=n-1; j>=0; j--) {
                if (matrix[i][j]=='1') {
                    right[j] = Math.min(right[j],cur_right);
                } else {
                    right[j]=n;
                    cur_right = j;
                }
            }

            for (int j = 0; j < n; j++) {
                maxare = Math.max(maxare,((right[j]-left[j])*height[j]));
            }
        }

        return maxare;
    }

    public static void main(String[] args) {
        char[][] s = {{'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}};

        System.out.println(maximalRectangle(s));
    }
}
